#ifndef HEAD_H
#define HEAD_H
#include<iostream>
#include<string>
#include<queue>
using namespace std;

struct node{
    char c;
    node* lChlid;
    node* rChild;
};

int search(string str,char c){
    for(int i=0;i<str.length();i++)
        if(str[i]==c) return i;
    return -1;
}

node* pre_in_createTree(string pre,string in){
    if(pre=="")return NULL;
    node *pointer = new node;
    if(pre.length()==1)
        pointer->c=pre[0];
    else{
        int index=search(in,pre[0]);
        node *left=pre_in_createTree(pre.substr(1,index),in.substr(0,index));
        node *right=pre_in_createTree(pre.substr(index+1,pre.length()-index-1),in.substr(index+1,in.length()-index-1));
        pointer->c=pre[0];
        pointer->lChlid=left;
        pointer->rChild=right;
    }
    return pointer;
}

node* in_post_createTree(string in,string post){
    if(post=="")return NULL;
    node*pointer= new node;
    if(post.length()==1)
        pointer->c=post[post.length()];
    else{
        int index=search(in,post[post.length()]);
        node *left=in_post_createTree(in.substr(0,index),post.substr(0,index));
        node *right=in_post_createTree(in.substr(index+1,in.length()),post.substr(index,post.length()-1));
        pointer->c=post[post.length()];
        pointer->lChlid=left;
        pointer->rChild=right;
    }
    return pointer;
}

void show(node* pointer){
    using std::queue;
    queue<node*>nodeQueue;
    node* p=pointer;
    nodeQueue.push(p);
    while(!nodeQueue.empty()||p){
        p=nodeQueue.front();
        cout<<p->c<<"\t";
        nodeQueue.pop();
    if(p->lChlid)
        nodeQueue.push(p->lChlid);
    if(p->rChild)
        nodeQueue.push(p->rChild);

    }
}

#endif // HEAD_H
